package main

import (
	"fmt"
	"sort"
	"strconv"
)

// 合并多个LinkList
func main() {
	l1 := strToLink2("5")
	l2 := strToLink2("124")

	//l2 = l2.Add(5, 2)  // midnode
	//l2 = l2.Add(-1, 0) // firstnode
	//l2 = l2.Add(9, 5)  // lastnode
	//fmt.Println(l2)
	//
	//l2 = l2.Remove(5) // lastnode
	//fmt.Println(l2)
	//l2 = l2.Remove(0) // firstnode
	//fmt.Println(l2)
	//l2 = l2.Remove(2) //midnode
	//fmt.Println(l2)
	//l2 = l2.Append(1)
	//fmt.Println(l2)
	//l2 = l2.Append(2)
	//fmt.Println(l2)

	l2 = strToLink2("12")
	l2 = l2.Swap(0, 1)

	l2 = strToLink2("123456")
	l2 = l2.Swap(0, 3)

	l2 = strToLink2("123456")
	l2 = l2.Swap(1, 2)

	l2 = strToLink2("12345")
	l2 = l2.Swap(0, 1)
	l2 = l2.Swap(2, 3)
	l2 = l2.Swap(4, 5)

	//fmt.Println(l2)

	l2 = strToLink2("12345")
	l2 = SwapEach(l2)
	fmt.Println(l2)
	l2 = swapPairs(l2)
	fmt.Println(l2)

	l3 := strToLink2("124")
	result := mergeKLists([]*ListNode{l1, l2, l3})
	fmt.Println(result)
}
func swapPairs(head *ListNode) *ListNode {
	// 节点数小于2，直接返回
	if head == nil || head.Next == nil {
		return head
	}
	newHead := &ListNode{}
	newHead.Next = head
	pre := newHead
	// 但前节点
	curr := head
	for curr != nil && curr.Next != nil {
		// 当前节点的下一节点
		next := curr.Next
		// 下下一个节点
		nextNext := curr.Next.Next
		// 交换当前节点和当前节点的下一节点
		pre.Next = next
		pre.Next.Next = curr
		// 更新下次交换的当前节点的前置节点
		pre = pre.Next.Next
		// 更新当前节点下一节点
		curr.Next = nextNext
		// 更新当前节点
		curr = curr.Next
	}
	return newHead.Next
}

// 相互交换
func SwapEach(l *ListNode) *ListNode {
	i, j, len := 0, 1, 0

	other := l
	for other != nil {
		len++
		other = other.Next
	}

	for i < j && j < len {
		l = l.Swap(i, j)
		i += 2
		j += 2
	}
	fmt.Println(l)
	return l
}

func mergeKLists(lists []*ListNode) *ListNode {
	result := &ListNode{}
	other := result
	var arr []int

	for _, v := range lists {
		for v != nil {
			if v != nil {
				arr = append(arr, v.Val)
			}

			if v != nil {
				v = v.Next
			}
		}
	}

	sort.Ints(arr)

	for _, v := range arr {
		other.Next = &ListNode{v, nil}
		other = other.Next
	}

	return result.Next
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func (l *ListNode) Add(value, index int) *ListNode {
	i := 0

	if index == 0 { //first node
		root := &ListNode{value, l}
		return root
	}
	other := l
	for other != nil {
		i++
		if i == index {
			node1 := other.Next
			newnode := &ListNode{value, nil}
			other.Next = newnode
			newnode.Next = node1
		}
		other = other.Next
	}
	return l
}

func (l *ListNode) Append(value int) *ListNode {

	if l == nil {
		return &ListNode{value, nil}
	}
	other := l

	lastNode := &ListNode{}
	for other != nil {
		lastNode = other
		other = other.Next
		if other == nil {
			break
		}
	}

	lastNode.Next = &ListNode{value, nil}
	return lastNode
}

func (l *ListNode) Remove(index int) *ListNode {
	other := l
	i := 0

	if index == 0 { //first node
		return l.Next
	}
	for other != nil {
		i++

		if index == i {
			if other.Next != nil {
				other.Next = other.Next.Next
			} else { // last node
				other.Next = nil
			}
		}

		other = other.Next
	}
	return l
}

// 交换两个node，边界，index1=0，只有两个元素时
func (l *ListNode) Swap(index1, index2 int) *ListNode {
	if l == nil {
		return l
	}
	other := l
	i := 0
	var node1, node1prev, node2, node2prev *ListNode

	if index1 >= index2 {
		return l
	}

	if index1 == 0 {
		node1 = l
		node1prev = nil
	}

	for other != nil {
		if index1-1 == i {
			node1prev = other
			node1 = node1prev.Next
		}
		if index2-1 == i {
			node2prev = other
			node2 = node2prev.Next
		}

		if node1 != nil && node2 != nil {
			break
		}
		i++
		other = other.Next
	}

	if node1 != nil && node2 != nil {
		if node1prev != nil {
			node1prev.Next = node2
		} else {
			l = node2
		}
		node1next := node1.Next
		node2next := node2.Next

		if node1next != node2 {
			node2.Next = node1next
		}
		if node2prev != node1 {
			node2prev.Next = node1
		} else {
			node2.Next = node1
		}
		node1.Next = node2next
	}
	return l
}

func (l *ListNode) String() string {
	lnode := l
	str := ""
	for lnode != nil {
		str += strconv.Itoa(lnode.Val) + "->"
		lnode = lnode.Next
	}
	return str
}

func strToLink2(str string) *ListNode {
	root := ListNode{0, nil}
	other := &root // 定义一个指针，指向第一个节点

	for i := 0; i < len(str); i++ {
		v2, _ := strconv.Atoi(string(str[i]))
		tmp := ListNode{v2, nil} // 创建临时节点
		other.Next = &tmp        // 首节点的next 指向临时节点
		other = &tmp             // other 向后移动一格
	}
	return root.Next

}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	result := &ListNode{}
	other := result
	var arr []int

	for l1 != nil || l2 != nil {
		if l2 != nil {
			arr = append(arr, l2.Val)
		}
		if l1 != nil {
			arr = append(arr, l1.Val)
		}

		if l1 != nil {
			l1 = l1.Next
		}
		if l2 != nil {
			l2 = l2.Next
		}
	}

	sort.Ints(arr)

	for _, v := range arr {
		other.Next = &ListNode{v, nil}
		other = other.Next
	}

	return result.Next
}
